#include "main/utils.h"
using namespace std;

bool isAlpha(char ch) {
  if ((ch >= 'a' && ch <= 'z') ||
      (ch >= 'A' && ch <= 'Z')) {
    return true;
  }
  return false;
}

bool isDigit(char ch) {
  if (ch >= '0' && ch <= '9') {
    return true;
  }
  return false;
}

bool isPalindromeCore(string str, int begin, int end) {
  while (begin <= end) {
    while (!isAlpha(str[begin]) && !isDigit(str[begin])) {
      ++begin;
    }
    while (!isAlpha(str[end]) && !isDigit(str[end])) {
      --end;
    }
    if (str[begin] != str[end]) {
      return false;
    }
    ++begin;
    --end;
  }
  return true;
}

bool isPalindrome(string str) {
  transform(str.begin(), str.end(), str.begin(), ::toupper);
  int begin = 0, end = str.size() - 1;
  while (begin <= end) {
    while (!isAlpha(str[begin]) && !isDigit(str[begin])) {
      ++begin;
    }
    while (!isAlpha(str[end]) && !isDigit(str[end])) {
      --end;
    }
    if (str[begin] != str[end]) {
      return isPalindromeCore(str, begin + 1, end) ||
             isPalindromeCore(str, begin, end - 1);
    }
    ++begin;
    --end;
  }
  return true;
}

int main() {
  string str = "Was it a cat I saw";
  bool ret = isPalindrome(str);
  cout << ret << endl;

  str = "aghoettaeohga";
  ret = isPalindrome(str);
  cout << ret << endl;

  return 0;
}
